|
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into Euclidean space in such a way that no two cycles of the graph have nonzero linking number. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.〔.〕 Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding. Flat embeddings are automatically linkless, but not vice versa.〔 The complete graph ''K''6, the Petersen graph, and the other five graphs in the Petersen family do not have linkless embeddings.〔 The linklessly embeddable graphs are closed under graph minors〔 and Y-Δ transforms,〔 have the Petersen family graphs as their forbidden minors,〔.〕 and include the planar graphs and apex graphs.〔 They may be recognized, and a flat embedding may be constructed for them, in linear time.〔 ==Definitions== Two disjoint curves in Euclidean space are said to be unlinked if there is a continuous motion of the curves which transforms them into disjoint coplanar circles without one curve passing through the other or through itself. If there is no such continuous motion, they are said to be linked. The Hopf link, formed by two circles that each pass through the disk spanned by the other, forms the simplest example of a pair of linked curves, but it is possible for curves to be linked in other more complicated ways. If two curves are not linked, then it is possible to find a disk in space, bounded by the first curve and disjoint from the second curve, and conversely if such a disk exists then the curves are necessarily unlinked. The linking number of two closed curves in three-dimensional space is a topological invariant of the curves: it is a number, defined from the curves in any of several equivalent ways, that does not change if the curves are moved continuously without passing through each other. The version of the linking number used for defining linkless embeddings of graphs is found by projecting the embedding onto the plane and counting the number of crossings of the projected embedding in which the first curve passes over the second one, modulo 2.〔.〕 The projection must be "regular", meaning that no two vertices project to the same point, no vertex projects to the interior of an edge, and at every point of the projection where the projections of two edges intersect, they cross transversally; with this restriction, any two projections lead to the same linking number. The linking number of the unlink is zero, and therefore, if a pair of curves has nonzero linking number, the two curves must be linked. However, there are examples of curves that are linked but that have zero linking number, such as the Whitehead link. An embedding of a graph into three-dimensional space consists of a mapping from the vertices of the graph to points in space, and from the edges of the graph to curves in space, such that each endpoint of each edge is mapped to an endpoint of the corresponding curve, and such that the curves for two different edges do not intersect except at a common endpoint of the edges. Any finite graph has a finite (though perhaps exponential) number of distinct simple cycles, and if the graph is embedded into three-dimensional space then each of these cycles forms a simple closed curve. One may compute the linking number of each disjoint pair of curves formed in this way; if all pairs of cycles have zero linking number, the embedding is said to be linkless.〔; ; .〕 In some cases, a graph may be embedded in space in such a way that, for each cycle in the graph, one can find a disk bounded by that cycle that does not cross any other feature of the graph. In this case, the cycle must be unlinked from all the other cycles disjoint from it in the graph. The embedding is said to be flat if every cycle bounds a disk in this way.〔. A similar definition of a "good embedding" appears in ; see also and .〕 A flat embedding is necessarily linkless, but there may exist linkless embeddings that are not flat: for instance, if ''G'' is a graph formed by two disjoint cycles, and it is embedded to form the Whitehead link, then the embedding is linkless but not flat. A graph is said to be intrinsically linked if, no matter how it is embedded, the embedding is always linked. Although linkless and flat embeddings are not the same, the graphs that have linkless embeddings turn out to be the same as the graphs that have flat embeddings.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「linkless embedding」の詳細全文を読む スポンサード リンク
|